package 链表;

// https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
// 4->1->8->4->5
// 5->0->1->8->4->5
// => 8->4->5
public class _160_相交链表 {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 1)由于双链长度互补,所以在第二轮从交换链表出发后必同时走到相交的节点
        // 2)若是双链长度相等且有相交节点,第一轮即找出相交节点
        // 3)若是长度相同的链表不相交,第一轮跑完即会pA==pB==null
        // 4)若是长度不同且不相交的链表,也是由于双链长度互补,第二轮双链将同时走至null
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(1);
        head.next.next = new ListNode(8);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode head2 = new ListNode(5);
        head2.next = new ListNode(0);
        head2.next.next = new ListNode(1);
        head2.next.next.next = head.next.next;

        System.out.println(head);
        System.out.println(head2);
//        ListNode newHead = mergeTwoLists(head, head2);
        ListNode newHead = getIntersectionNode(head, head2);
        System.out.println(newHead);
    }
}
